﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace HerbertDotNet
{
    public class HerbertInterpreter : ICloneable
    {
        protected int _whiteButtonsPressedHighest; // Highest number of white buttons pressed.

        protected int _maxIterations;              // Maximum number of iterations since last score increase
        // before terminating execution.
        protected int _maxCallArguments;           // Maximum number of call arguments before terminating
        // execution.

        public HerbertInterpreter(HerbertLevel level, int maxIterations)
            : this(level)
        {
            _maxIterations = maxIterations;
        }

        public HerbertInterpreter(HerbertLevel level)
            : this()
        {
            this.Level = level;
        }

        public HerbertInterpreter()
        {
            _maxIterations = 100000;
            _maxCallArguments = 10000;

            this.ReportPressedButtons = false;
            this.TraceExecution = false;
        }

        public bool ReportPressedButtons
        {
            get;
            set;
        }

        public bool TraceExecution
        {
            get;
            set;
        }

        public int MaxIterations
        {
            get { return _maxIterations; }
            set { _maxIterations = value; }
        }

        public int MaxCallArguments
        {
            get { return _maxCallArguments; }
            set { _maxCallArguments = value; }
        }

        public HerbertProgram Program
        {
            get;
            set;
        }

        public HerbertLevel Level
        {
            get;
            set;
        }

        public int Run()
        {
            // Get next state until program has terminated.
            IEnumerable<HProgramRunState?> states = GetProgramRunStates();
            IEnumerator<HProgramRunState?> enumerator = states.GetEnumerator();

            while (enumerator.MoveNext())
                ;

            return CalculateScore();
        }

        public int CalculateScore()
        {
            HerbertLevel level = this.Level;

            // Calculate score acheived by program.
            int score;
            int progByteLength = this.Program.GetByteLength();

            if (_whiteButtonsPressedHighest == level.TotalWhiteButtons
                && progByteLength <= level.ProgramMaxByteLength)
            {
                // Level has been solved.
                try
                {
                    score = (level.Points * level.ProgramMaxByteLength) / progByteLength;
                }
                catch (DivideByZeroException)
                {
                    return 0;
                }
            }
            else
            {
                // Level has not been solved.
                int pointsPerButton = 0;

                if (progByteLength <= level.ProgramMaxByteLength)
                    pointsPerButton = level.Points / (2 * level.TotalWhiteButtons);
                else if (progByteLength <= (level.ProgramMaxByteLength << 1))
                    pointsPerButton = level.Points * (2 * level.ProgramMaxByteLength - progByteLength) /
                        (2 * level.ProgramMaxByteLength * level.TotalWhiteButtons);

                score = _whiteButtonsPressedHighest * pointsPerButton;
            }

            // Return score.
            return score;
        }

        public IEnumerable<HProgramRunState?> GetProgramRunStates()
        {
            HerbertProgram program = this.Program;

            // Check that program exists and has been compiled.
            if (program == null) throw new InvalidOperationException(
                "No program exists to be executed.");

            if (!program.IsCompiled) throw new InvalidOperationException(
                "The program must be compiled before it can be run.");

            // Variables for running program.
            HStack stack = new HStack();
            int dataUb = program.Code.GetUpperBound(0);
            int programCounter = program.StartAddress;
            int lastProgramCounter = program.StartAddress;
            HInstruction curInstruction = HInstruction.NoOp;
            HInstruction lastInstruction;

            bool insideProcedureDeclaration = false;
            int curProcedureName = -1; // Only set when inside parameters of called procedure.
            int curEvalArgument = -1;
            bool callProcedure = false;
            Dictionary<int, object> arguments = new Dictionary<int, object>();
            Dictionary<int, object> callArguments = null;
            bool insideArgument = false;
            int argumentDepth = 0;
            int callArgIndex = -1;
            List<HInstruction> curArgCommands = null;
            int curArgNumber = int.MinValue;

            bool curIterationYielded = false;
            int iterationsCounter = 0;

            // Variables for level and robot.
            const HerbertLevel.Tile allWalls = HerbertLevel.Tile.WallTop | HerbertLevel.Tile.WallBottom
                | HerbertLevel.Tile.WallLeft | HerbertLevel.Tile.WallRight;

            HerbertLevel level = this.Level;
            HPoint curPosition = level.StartPosition;
            HDirection curDirection = HDirection.Up;
            HPoint lastPosition = curPosition;
            HDirection lastDirection = curDirection;
            bool[,] pressedButtons = new bool[HerbertLevel.TilesWidth, HerbertLevel.TilesHeight];
            int whiteButtonsPressed = 0;

            _whiteButtonsPressedHighest = 0;

            try
            {
                // Execute instructions until end of program is reached.
                // It is important that the loop iterates until programCounter is 1 greater that address of
                // last instruction, so that lastInstruction can be checked to execute a procedure.
                while (programCounter <= dataUb + 1 || curEvalArgument != -1)
                {
                    curIterationYielded = false;

                    // Check whether to trace execution and whether program counter has changed.
                    if (this.TraceExecution && programCounter != lastProgramCounter
                        && curEvalArgument == -1)
                    {
                        var pcInstruction = programCounter <= dataUb ? program.Code[programCounter]
                            : HInstruction.NoOp;

                        // Check type of current instruction.
                        if ((pcInstruction == HInstruction.Straight
                            || pcInstruction == HInstruction.Left
                            || pcInstruction == HInstruction.Right
                            || (pcInstruction & HInstruction.ProcedureNameBase) != 0
                            || (pcInstruction & HInstruction.ParameterNameBase) != 0))
                        {
                            // If current is parameter name, insure that parameter is imperative.
                            if ((pcInstruction & HInstruction.ParameterNameBase) == 0
                                || !(arguments[(int)(pcInstruction ^ HInstruction.ParameterNameBase)]
                                is int))
                            {
                                // Return new run state.
                                yield return new HProgramRunState(curEvalArgument == -1 ?
                                    programCounter : -1, curPosition, curDirection,
                                    this.ReportPressedButtons ? (bool[,])pressedButtons.Clone() : null);

                                curIterationYielded = true;
                            }
                        }
                    }

                    // Check if current iteration has already yielded.
                    if (!curIterationYielded)
                    {
                        // Check if position or direction of robot has changed.
                        if (curPosition != lastPosition || curDirection != lastDirection)
                        {
                            // Return new run state.
                            yield return new HProgramRunState(curEvalArgument == -1 ?
                                programCounter : -1, curPosition, curDirection,
                                this.ReportPressedButtons ? (bool[,])pressedButtons.Clone() : null);

                            curIterationYielded = true;
                        }
                    }

                    try
                    {
                        // Exit loop if all white buttons have been pressed.
                        if (whiteButtonsPressed == level.TotalWhiteButtons && level.TotalWhiteButtons != 0)
                            break;

                        // Exit loop if number of iterations since last increase of highest number of white
                        // buttons pressed is too high.
                        iterationsCounter++;
                        if (iterationsCounter == _maxIterations) break;

                        // Exit loop if number of call arguments is too large.
                        if (callArguments != null && callArguments.Count > _maxCallArguments) break;
                        if (curArgCommands != null && curArgCommands.Count > _maxCallArguments) break;

                        // Set last program counter and instruction.
                        lastProgramCounter = programCounter;
                        lastInstruction = curInstruction;

                        // Set last position, and direction.
                        lastPosition = curPosition;
                        lastDirection = curDirection;

                        // Get current instruction.
                        if (curEvalArgument == -1)
                            curInstruction = (programCounter <= dataUb) ? program.Code[programCounter]
                                : HInstruction.NoOp;
                        else
                        {
                            if (arguments.Count != 0)
                            {
                                List<HInstruction> argCommands = (List<HInstruction>)arguments[
                                    curEvalArgument];

                                // Setting current instruction to EndProcedure will stop evaluating current
                                // procedural argument.
                                curInstruction = (programCounter < argCommands.Count) ? argCommands[
                                    programCounter] : HInstruction.EndProcedure;
                            }
                            else
                            {
                                curInstruction = HInstruction.EndProcedure;
                            }
                        }

                        // Check if current position is inside procedure declaration.
                        if (insideProcedureDeclaration)
                        {
                            // Check if current instruction is EndProcedure.
                            if (curInstruction == HInstruction.EndProcedure)
                            {
                                // Set that current position is outside procedure declaration.
                                insideProcedureDeclaration = false;
                            }

                            // Increment program counter.
                            programCounter++;

                            continue;
                        }

                        // Check if currently executing procedure.
                        if (curProcedureName != -1)
                        {
                            // Check if last instruction might have marked end of procedure call.
                            if (lastInstruction == HInstruction.EndArgument
                                || ((int)(lastInstruction & HInstruction.ProcedureNameBase) != 0))
                            {
                                // Check that there are no more arguments to be found.
                                if (curInstruction != HInstruction.BeginArgument && !insideArgument)
                                {
                                    // Check if argument depth is zero.
                                    if (argumentDepth == 0)
                                    {
                                        // Check whether to call procedure.
                                        if (callProcedure)
                                        {
                                            // Push all arguments onto stack.
                                            object arg;

                                            foreach (KeyValuePair<int, object> kvPair in arguments)
                                            {
                                                arg = kvPair.Value;

                                                // Check if current argument is number or command array.
                                                if (arg is int)
                                                {
                                                    stack.Push(((int)arg << 1) | 0x0001);
                                                }
                                                else
                                                {
                                                    List<HInstruction> argCommands = (List<HInstruction>)arg;

                                                    for (int i = argCommands.Count - 1; i >= 0; i--)
                                                        stack.Push((int)argCommands[i]);

                                                    stack.Push(argCommands.Count << 1);
                                                }

                                                // Push name of argument onto stack.
                                                stack.Push(kvPair.Key);
                                            }

                                            // Push argument count onto stack
                                            stack.Push(arguments.Values.Count);

                                            // Push index of current call argument onto stack.
                                            stack.Push(callArgIndex);

                                            // Push index of currently evaluating argument onto stack.
                                            stack.Push(curEvalArgument);

                                            // Push current procedure name onto stack.
                                            stack.Push(curProcedureName);

                                            // Push program counter onto stack.
                                            stack.Push(programCounter - 1);

                                            // Set dictionary of current arguments to call arguments.
                                            arguments = callArguments;

                                            // Jump to called procedure.
                                            programCounter = program.Procedures[curProcedureName]
                                                .BodyAddress;
                                            lastInstruction = HInstruction.NoOp;
                                            curProcedureName = -1;
                                            curEvalArgument = -1;

                                            continue;
                                        }
                                    }
                                }
                            }

                            // Check if current position is inside arugment.
                            if (insideArgument)
                            {
                                // Check if current instruction is EndArgument and argument depth is zero.
                                if (curInstruction == HInstruction.EndArgument && argumentDepth == 0)
                                {
                                    insideArgument = false;

                                    // Add argument to list of current arguments.
                                    int curArgName = program.Procedures[curProcedureName].ArgumentNames[
                                        callArgIndex];

                                    if (curArgNumber == int.MinValue)
                                    {
                                        // Add argument to dictionary of call arguments.
                                        callArguments.Add(curArgName, curArgCommands);
                                    }
                                    else
                                    {
                                        // Do not call procedure if argument is zero or negative.
                                        if (curArgNumber <= 0) callProcedure = false;

                                        // Add argument to dictionary of call arguments.
                                        callArguments.Add(curArgName, curArgNumber);
                                    }
                                }
                                else
                                {
                                    // Check if instruction should be evaluated or simply stored.
                                    int curNumber = int.MinValue;
                                    List<HInstruction> paramCommands = null;

                                    if ((curInstruction & HInstruction.NumberBase) != 0)
                                    {
                                        // Get number from instruction.
                                        curNumber = (int)(curInstruction ^ HInstruction.NumberBase);
                                    }
                                    else if ((curInstruction & HInstruction.ParameterNameBase) != 0)
                                    {
                                        // Get value of parameter.
                                        int paramName = (int)(curInstruction
                                            ^ HInstruction.ParameterNameBase);

                                        if (arguments[paramName] is int)
                                            curNumber = (int)arguments[paramName];
                                        else
                                            paramCommands = (List<HInstruction>)arguments[paramName];
                                    }

                                    // Check whether argument was evaluated.
                                    if (curNumber == int.MinValue)
                                    {
                                        // Check if current instruction is parameter.
                                        if (paramCommands != null)
                                        {
                                            // Add list of commands held by parameter to current argument.
                                            curArgCommands.AddRange(paramCommands);
                                        }
                                        else
                                        {
                                            // Check if instruction is operator.
                                            if (curInstruction == HInstruction.Add
                                                || curInstruction == HInstruction.Subtract)
                                            {
                                                // Check operator is first instruction of argument.
                                                if (lastInstruction == HInstruction.BeginArgument)
                                                    curArgNumber = 0;
                                            }
                                            else
                                            {
                                                // Check if current instruction marks start or end of 
                                                // argument.
                                                if (curInstruction == HInstruction.BeginArgument)
                                                {
                                                    // Increment argument depth.
                                                    argumentDepth++;
                                                }
                                                else if (curInstruction == HInstruction.EndArgument)
                                                {
                                                    // Check if number exists to write to current argument.
                                                    if (curArgNumber != int.MinValue)
                                                    {
                                                        // Write number to current argument.
                                                        curArgCommands.Add(HInstruction.NumberBase
                                                            | (HInstruction)curArgNumber);

                                                        curArgNumber = int.MinValue;
                                                    }

                                                    // Decrement argument depth.
                                                    argumentDepth--;
                                                }

                                                // Add instruction to current argument.
                                                curArgCommands.Add(curInstruction);
                                            }
                                        }
                                    }
                                    else
                                    {
                                        switch (lastInstruction)
                                        {
                                            case HInstruction.Add:
                                                curArgNumber += curNumber;
                                                break;
                                            case HInstruction.Subtract:
                                                curArgNumber -= curNumber;
                                                break;
                                            case HInstruction.BeginArgument:
                                                // Number is first instruction of argument.
                                                curArgNumber = curNumber;
                                                break;
                                        }
                                    }
                                }

                                // Increment program counter.
                                programCounter++;

                                continue;
                            }
                        }

                        // Check current instruction.
                        switch (curInstruction)
                        {
                            case HInstruction.NoOp:
                                // Stop executing program.
                                programCounter = int.MaxValue;
                                continue;
                            case HInstruction.Straight:
                                // Move robot according to its current direction.
                                if (curDirection == HDirection.Up && curPosition.Y > 0)
                                    curPosition.Y--;
                                else if (curDirection == HDirection.Down && curPosition.Y <
                                    HerbertLevel.TilesHeight - 1)
                                    curPosition.Y++;
                                else if (curDirection == HDirection.Left && curPosition.X > 0)
                                    curPosition.X--;
                                else if (curDirection == HDirection.Right && curPosition.X <
                                    HerbertLevel.TilesWidth - 1)
                                    curPosition.X++;

                                HerbertLevel.Tile curTile = level.Tiles[curPosition.X, curPosition.Y];

                                // Disallow move if robot hits wall.
                                if ((curTile & allWalls) != 0)
                                    curPosition = lastPosition;

                                // Check if robot has pressed button.
                                if (curTile == HerbertLevel.Tile.WhiteButton)
                                {
                                    // Check if button was previously unpressed.
                                    if (!pressedButtons[curPosition.X, curPosition.Y])
                                    {
                                        // Set that this button has been pressed.
                                        pressedButtons[curPosition.X, curPosition.Y] = true;

                                        // Increment count of white buttons pressed.
                                        whiteButtonsPressed++;

                                        // Check if highest number of white buttons have been pressed.
                                        if (whiteButtonsPressed > _whiteButtonsPressedHighest)
                                        {
                                            // Set new highest number of white buttons pressed.
                                            _whiteButtonsPressedHighest = whiteButtonsPressed;

                                            // Reset iterations counter.
                                            iterationsCounter = 0;
                                        }
                                    }
                                }
                                else if (curTile == HerbertLevel.Tile.GrayButton)
                                {
                                    // Reset number of whit ebuttons pressed.
                                    whiteButtonsPressed = 0;

                                    // Clear array of pressed buttons.
                                    Array.Clear(pressedButtons, 0, pressedButtons.Length);
                                }

                                break;
                            case HInstruction.Left:
                                // Rotate direction of robot to left.
                                if (curDirection == HDirection.Up) curDirection = HDirection.Left;
                                else if (curDirection == HDirection.Down) curDirection = HDirection.Right;
                                else if (curDirection == HDirection.Left) curDirection = HDirection.Down;
                                else if (curDirection == HDirection.Right) curDirection = HDirection.Up;

                                break;
                            case HInstruction.Right:
                                // Rotate direction of robot to right.
                                if (curDirection == HDirection.Up) curDirection = HDirection.Right;
                                else if (curDirection == HDirection.Down) curDirection = HDirection.Left;
                                else if (curDirection == HDirection.Left) curDirection = HDirection.Up;
                                else if (curDirection == HDirection.Right) curDirection = HDirection.Down;

                                break;
                            case HInstruction.BeginProcedure:
                                // Set that current position is inside procedure.
                                insideProcedureDeclaration = true;

                                break;
                            case HInstruction.EndProcedure:
                                // Note: This code will not be reached if the EndProcedure is for a 
                                // procedure definition.

                                lastInstruction = HInstruction.NoOp;

                                // Pop program counter off stack.
                                programCounter = stack.Pop();

                                // Pop current procedure name off stack.
                                curProcedureName = stack.Pop();

                                // Pop index of currently evaluating argument off stack.
                                curEvalArgument = stack.Pop();

                                // Pop index of current call argument off stack.
                                callArgIndex = stack.Pop();

                                // Check how many arguments are on stack.
                                int argCount = stack.Pop();

                                if (argCount == 0) break;

                                // Pop arguments off stack.
                                int arg;
                                int argName;

                                arguments = new Dictionary<int, object>();

                                for (int argIndex = 0; argIndex < argCount; argIndex++)
                                {
                                    // Pop next argument off stack.
                                    argName = stack.Pop();
                                    arg = stack.Pop();

                                    // Check if argument is number or list of commands.
                                    if ((arg & 0x0001) != 0)
                                    {
                                        arguments.Add(argName, (arg & 0xFFFE) >> 1);
                                    }
                                    else
                                    {
                                        int commandCount = arg >> 1;
                                        List<HInstruction> argCommands = new List<HInstruction>(
                                            commandCount);

                                        for (int i = 0; i < commandCount; i++)
                                            argCommands.Add((HInstruction)stack.Pop());

                                        arguments.Add(argName, argCommands);
                                    }
                                }

                                break;
                            case HInstruction.BeginArgument:
                                // Reset argument variables.
                                insideArgument = true;
                                callArgIndex++;
                                curArgCommands = new List<HInstruction>();
                                curArgNumber = int.MinValue;

                                break;
                            default:
                                // Check if instruction is procedure name.
                                if ((curInstruction & HInstruction.ProcedureNameBase) != 0)
                                {
                                    var tempProcName = (int)(curInstruction
                                        ^ HInstruction.ProcedureNameBase);

                                    if (!program.Procedures.ContainsKey(tempProcName))
                                        throw new HerbertRuntimeException(string.Format(
                                            "The procedure '{0}' is not defined in the program code.",
                                            HerbertHelper.ProcedureNames[tempProcName]));

                                    // Store name of current procedure.
                                    curProcedureName = tempProcName;
                                    callProcedure = true;

                                    // Create new dictionary of call arguments.
                                    callArguments = new Dictionary<int, object>();
                                    callArgIndex = -1;
                                    insideArgument = false;
                                }

                                // Check if instruction is parameter name.
                                if ((curInstruction & HInstruction.ParameterNameBase) != 0)
                                {
                                    // Push null argument count onto stack.
                                    stack.Push(0);

                                    // Push index of current call argument onto stack.
                                    stack.Push(callArgIndex);

                                    callArgIndex = -1;
                                    insideArgument = false;

                                    // Push index of currently evaluating argument onto stack.
                                    stack.Push(curEvalArgument);

                                    // Push current procedure name onto stack.
                                    stack.Push(curProcedureName);

                                    // Push program counter onto stack.
                                    stack.Push(programCounter);

                                    // Set current argument to evaluate.
                                    curEvalArgument = (int)(curInstruction ^ HInstruction.ParameterNameBase);

                                    // Jump to first instruction of evaluating argument.
                                    programCounter = 0;

                                    continue;
                                }

                                break;
                        }

                        // Increment program counter.
                        programCounter++;
                    }
                    catch (Exception ex)
                    {
                        var exRuntime = ex as HerbertRuntimeException;

                        throw new HerbertRuntimeException(string.Format(
                            "Error executing program."
                            + (exRuntime == null ? string.Empty : "\r\n" + exRuntime.Message),
                            programCounter), exRuntime == null ? ex : null);
                    }
                }
            }
            finally
            {
                // Perform garbage collection on execution stack.
                stack = null;
                GC.Collect();
            }
        }

        public object Clone()
        {
            var obj = new HerbertInterpreter();

            obj.Level = this.Level;
            obj.Program = this.Program;
            obj.MaxIterations = this.MaxIterations;
            obj.MaxCallArguments = this.MaxCallArguments;
            obj.ReportPressedButtons = this.ReportPressedButtons;

            return obj;
        }

        protected class HStack : Stack<int>
        {
            protected const int _capacity = 0x4000; // Capacity of stack. (64 KB)

            public HStack()
                : base(_capacity)
            {
            }

            public int Capacity
            {
                get { return _capacity; }
            }

            new void Push(int item)
            {
                // Clear stack if it is full.
                if (this.Count == _capacity) Clear();

                // Push item onto stack.
                base.Push(item);
            }
        }
    }

    public struct HProgramRunState
    {
        public int ProgramCounter;     // Value of program counter.
        public HPoint Position;        // Position of robot.
        public HDirection Direction;   // Direction that robot faces.
        public bool[,] PressedButtons; // Array of pressed white buttons.

        public HProgramRunState(int programCounter, HPoint position, HDirection direction,
            bool[,] pressedButtons)
        {
            this.ProgramCounter = programCounter;
            this.Position = position;
            this.Direction = direction;
            this.PressedButtons = pressedButtons;
        }
    }

    public enum HDirection
    {
        Up,
        Left,
        Down,
        Right
    }
}
